package com.xinpan.exercise;

import java.util.ArrayList;

public class NQueens {
    public ArrayList<String[]> solveNQueens(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(n == 0)
            return null;
        
        ArrayList<Integer[]> res = new ArrayList<Integer[]>();
        for(int i = 0; i < n; i++)
        {
            Integer[] aRes = new Integer[n];
            aRes[0] = i;
            res.add(aRes);
        }
        
        ArrayList<Integer[]> newRes = subSolve(res, n, 1);
        
        ArrayList<String[]> fRes = new ArrayList<String[]>();
        for(int i = 0; i < newRes.size(); i++)
        {
            Integer[] nRes = newRes.get(i);
            String[] aFRes = new String[n];
            for(int j = 0; j < n; j++)
            {
                String str = "";
                for(int k = 0; k < n; k++)
                {
                    if(k == nRes[j])
                        str += "Q";
                    else
                        str += ".";
                }
                aFRes[j] = str;
            }
            fRes.add(aFRes);
        }
        
        return fRes;
    }
    
    public ArrayList<Integer[]> subSolve(ArrayList<Integer[]> res, int n, int l)
    {
        if(l == n)
            return res;
        
        ArrayList<Integer[]> newRes = new ArrayList<Integer[]>();
        
        for(int i = 0; i < res.size(); i++)
        {
            Integer[] aRes = res.get(i);
            for(int j = 0; j < n; j++)
            {
                int k = 0;
                for(; k < l; k++)
                {
                    if(aRes[k] == j)
                        break;
                    if(aRes[k] + (l-k) == j ||
                        aRes[k] - (l-k) == j)
                        break;
                }
                if(k == l)
                {
                    Integer[] newARes = new Integer[n];
                    for(int m = 0; m < l; m++)
                        newARes[m] = aRes[m];
                    newARes[l] = j;
                    newRes.add(newARes);
                }
            }
        }
        
        return subSolve(newRes, n, l+1);
    }
}
